package com.gitee.feizns.explore.data_structure.linked_list.singly.getIntersectionNode;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author feizns
 * @since 2020/3/5
 */
public class GetIntersectionNode {

    public static void main(String[] args) {
        ListNode a = createA();
        ListNode b = createB();
        final ListNode node3 = getIntersectionNode3(a, b);
        System.out.println(node3.val);
    }

    private static ListNode a = new ListNode(3);

    static {
        a.next = new ListNode(4);
    }

    private static ListNode createA() {
        ListNode t = new ListNode(1);
        t.next = new ListNode(2);
        t.next.next = a;
        return t;
    }

    private static ListNode createB() {
        ListNode w = new ListNode(1);
        w.next = a;
        return w;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodeSet = new HashSet<>();
        ListNode tmp = headA;
        while ( tmp != null ) {
            nodeSet.add(tmp);
            tmp = tmp.next;
        }

        ListNode tmp2 = headB;
        while ( tmp2 != null ) {
            if ( nodeSet.contains(tmp2) )
                return tmp2;
            tmp2 = tmp2.next;
        }
        return null;
    }

    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while ( a != b ) {

        }
        return a;
    }

    private static ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while (p != q){
            p = p == null ? headB : p.next;
            q = q == null ? headA : q.next;
        }
        return p;
    }

}
